package sort;


import java.util.Random;

/**
 * @Auther: MFM
 * @Date: 2022/3/15 - 03 - 15 - 18:27
 * @version: 1.0
 */

public class ChangeSort {
    /*
     * 交换排序
     * */

    //冒泡排序
    public void BubbleSort(int[] arr) {
        if (arr == null) {
            return;
        }

        int length = arr.length;

        while (length != 1) {
            for (int j = 0; j < length - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    change(arr, j, j + 1);
                }
            }
            length--;
        }
    }

    //用于将int数组中i位置和j位置的数据进行交换的方法
    public void change(int[] arr, int i, int j) {
        if (arr == null) {
            return;
        }

        int e = arr[i];
        arr[i] = arr[j];
        arr[j] = e;
    }

    //单路排序
    public void QuickSort(int[] arr, int start, int end) {
        if (arr == null) {
            return;
        }

        //当出现 start > end 时 无法排序（start和end之间 只有一个数时） 直接返回
        if (start > end) {
            return;
        }

        int l = start;
        int r = end;

        //基准数一直为左
        int pivot = arr[start];

        while (l != r) {
            //先右往左循环
            while (arr[r] >= pivot && l < r) {
                r--;
            }
            //再左往右循环
            while (arr[l] < pivot && l < r) {
                l++;
            }

            change(arr, l, r);

        }
        //跳出循环意味着上述条件已经不成立了 不成立代表 l=j

        change(arr, start, l);

        QuickSort(arr, start, l - 1);

        QuickSort(arr, l + 1, end);

    }

    //双路快排
    public void DQuickSort(int[] arr, int start, int end) {
        int l = start;
        int r = end;

        int pivot = arr[(start + end) / 2];

        while (l < r) {
            while (arr[l] < pivot) {
                l++;
            }

            while (arr[r] > pivot) {
                r--;
            }

            if (l >= r) {
                break;
            }


            change(arr, l, r);

            //防止两个等于pivot的值一直压栈导致栈溢出
            if (arr[l] == pivot) {
                r--;
            }

            if (arr[r] == pivot) {
                l++;
            }
        }

        //基准点排除 如果不排除基准点 就会 在还剩两个元素时 无限压栈
        if (l == r) {
            l++;
            r--;
        }

        if (r > start) {
            DQuickSort(arr, start, r);
        }

        if (end > l) {
            DQuickSort(arr, l, end);
        }
    }

    public static void main(String[] args) {
        /* 测试结果
         *  1000000 排序所用时间为
         *  冒泡  大于1min
         *  快排（单路） 100+ms
         *  快排（双路） 100+ms
         **/
        int[] arr = new int[1000000];
        Random r = new Random();


        for (int i = 0; i < arr.length; i++) {
            arr[i] = r.nextInt();
        }

        long start = System.currentTimeMillis();

        new ChangeSort().QuickSort(arr, 0, arr.length - 1);

        long end = System.currentTimeMillis();

        System.out.println(end - start);


    }
}
